1. Field of the Invention
The present invention relates in general to a file retrieval system, and in particular, to a file retrieval system including a host-available device block map for optimally retrieving one or more blocks of data from a serpentine tape drive.
2. Description of Related Art
As computer technology develops, data storage systems have become more sophisticated and require the storage and retrieval of greater amounts of data. Even though disk-based storage systems have evolved significantly, such storage systems still have problems in terms of both cost and scalability.
The use of tape-based storage systems for data processing, backup, and/or archival purposes is well known in the art. For example, tape storage systems have traditionally been applied to sequential processing such as batch updating of master files. Tape storage systems also are used in data mining applications where thousands of queries are aggregated in one complete sequential scan of the data.
Advances in magnetic tape storage technology and devices have led to greatly increased capacity per cartridge. With the increase in capacity and new applications, there is a concomitant increase in the number of objects that may be stored per cartridge. indeed, the use of tape storage systems can be as much as two orders of magnitude more efficient than disk storage systems, in terms of cost per byte recorded and the number of bytes stored per unit (cartridge, etc.). However, one problem with tape storage systems is that the random access latency of tape is several orders of magnitude slower than disk storage systems.
New longitudinal tape formats such as IBM 3570 and IBM 3590 drives employ a tape track format described as serpentine longitudinal. These formats differ from previous IBM 3480/3490 drives in one regard by having higher track densities, thereby resulting in multiple tape passes in both the xe2x80x9coutxe2x80x9d and xe2x80x9cinxe2x80x9d directions.
In contrast, 18 track IBM 3480 drives write data only in the out direction and 36 track IBM 3490 drives write one set of tracks xe2x80x9coutxe2x80x9d and one set of tracks xe2x80x9cinxe2x80x9d. Optimized retrieval sequences for these devices comprise straightforward sequential ordering with no requirement for specialized ordering.
With IBM 3570 and IBM 3590 drives, however, there are 16 xe2x80x9coutxe2x80x9d and xe2x80x9cinxe2x80x9d tracks and 4 xe2x80x9coutxe2x80x9d and xe2x80x9cinxe2x80x9d tracks, respectively. Access to these tracks is accomplished by indexing the heads of the drive, a process that is very rapid as compared to searching the length of tape media.
In general, a serpentine longitudinal tape drive records data on a wrap (i.e., track) or a group of wraps in one direction along a length of the serpentine longitudinal tape media. Then, the tape drive reverses the recording direction and shifts its recording heads sideways a small distance to record another wrap or group of wraps in the opposite direction along the length of the tape. The tape drive continues these operations back and forth along the serpentine longitudinal tape media until all of the blocks of data are written.
Alternatively, instead of shifting its heads sideways a small distance to record another wrap or group of wraps, the serpentine longitudinal tape drive may electronically select another recording head or group of recording heads and move up the length of the tape media and continue back and forth until all of the blocks of data are written to the tape media. It will be appreciated, of course, that other types of recording techniques can be used as well.
As a result, a straightforward sequential retrieval order for serpentine longitudinal tape drives is most likely not optimized. The sequential retrieval order usually bears no relationship to the physical location of the blocks of data stored on serpentine tape media. Accordingly, the random retrieval of the blocks of data which are spaced apart on the serpentine tape can cause a significant latency. Indeed, for serpentine tape, the random retrieval of blocks of data spaced relatively far apart on the tape will likely result in grossly sub-optimal performance, if the blocks of data are retrieved in sequential order with respect to the order they were written.
Various techniques and systems for recording data on and retrieving data from a tape and for reducing access latency are known in the art. For example, the publication by Bruce K. Hillyer and Avi Silberschatz, entitled xe2x80x9cRandom I/O Scheduling in Online Tertiary Storage Systemsxe2x80x9d , ACM Conference, 1996, describes techniques for I/O scheduling for tape drives to resolve the problem of access latency. U.S. Pat. No. 5,485,321 issued to Leonhardt et al. entitled xe2x80x9cFormat and Method for Recording Optimizationxe2x80x9d discloses a serpentine recording technique for reducing access time. U.S. Pat. No. 5,373,485 issued to hogan et al. entitled xe2x80x9cMethod for Locating Data in a Data Cartridge Systemxe2x80x9d discloses a physical and logical block search for data on a serpentine pattern which eliminates search time. U.S. Pat. No. 5,121,270 issued to Alcudia et al. entitled xe2x80x9cMultitransducer Head Positioning Servo for Use in a Bi-directional Magnetic Tape Systemxe2x80x9d discloses a serpentine recording mode of operation. U.S. Pat. No. 4,858,039 issued to Mintzlaff entitled xe2x80x9cStreaming Tape Drive With Direct Block Addressabilityxe2x80x9d discloses reducing the time for retrieving a selected block of data recorded in a serpentine fashion. U.S. Pat. No. 4,796,20 issued to Glass et al. entitled xe2x80x9cSystem and Method for Encoding and Storing Digital Information on Magnetic Tapexe2x80x9d discloses a system for increasing the speed of serpentine tape writes and reads. Japanese publication JP 8-235775 (English abstract only) discloses a device for access to linear serpentine tape. Japanese publication JP 7-24443 (English abstract only) discloses shortening the access time to a file stored in a magnetic tape of a serpentine track system.
However, none of these patents or publications provide a completely satisfactory solution to the above mentioned problems in retrieving files stored on serpentine longitudinal tape media. It should thus be apparent that a need exists for methods for optimized file retrieval from serpentine longitudinal tape media.
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for optimizing the retrieval of blocks of data from a serpentine longitudinal tape media. A device block map (DBM) is stored on the tape media, wherein the DBM comprises a table having one or more rows and one or more columns for each block of data stored on the tape media. The columns are selected from a group comprising a wrap column, a position column, a logical block number column, and a file identifier column wherein the wrap column indicates a track where the block of data is recorded on the tape media, the position column indicates a physical position where the block of data is recorded on the tape media, the logical block number column indicates a logical block number for the block of data, and a file identifier column indicates a logical file identifier for the block of data. One or more retrieval paths for the blocks of data are determined from the device block map, wherein each of the retrieval paths comprises an ordered sequence of the blocks of data and the manner in which the tape media is to be traversed to accomplish the retrieval of the ordered sequence. A sum of distances is determined for each of the retrieval paths and an optimal one of the retrieval paths is selected based on the determined sum of distances. Thereafter, the blocks of data are retrieved from the tape media using the optimal retrieval path.
One advantage of the present invention is that it provides a significant improvement in the latency of random access to files stored on a serpentine longitudinal tape media. Another advantage is that the present invention provides a portable device block map which is accessible from the tape media.
Other advantages, features, and characteristics of the present invention; methods, operation, and functions of the related elements of the structure; combination of parts; and economies of manufacture will become apparent from the following detailed description of the preferred embodiments and accompanying drawings, all of which form a part of this specification, wherein like reference numerals designate corresponding parts in the various figures.